package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/delete-node-in-a-bst/">删除二叉搜索树中的节点 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-05 17:01
 */
public class DeleteNodeInABst_450 {

  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;

    if (key < root.val) { // 去左子树删除
      root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
      root.right = deleteNode(root.right, key);
    } else { // 找到当前节点时
      if (root.left == null) {
        return root.right; // 如果左子树为空直接返回右节点，相当于删除了当前节点
      } else if (root.right == null) {
        return root.left; // 返回左节点
      }
      // 此时代表要删除的节点需要做额外转换
      else {
        TreeNode cur = root.right;
        while (cur.left != null) { // 找到右孩子的最左节点
          cur = cur.left;
        }
        cur.left = root.left; // 将左子树节点挂在最左边
        root = root.right; // 当前右孩子为当前新的根
      }
    }
    return root;
  }
}
